#include <bits/stdc++.h>
#include "../../tools/tools.h"
using namespace std;


class Solution {

public:
    // 定义字典树节点
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        int cost;
        TrieNode() : cost(INT_MAX) {}
    };

    // 插入单词到字典树中
    void insert(TrieNode* root, const string& word, int cost) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->cost = min(node->cost, cost);
    }

    // 递归查找字典树
    void search(TrieNode* root, const string& target, int start, vector<int>& dp) {
        TrieNode* node = root;
        for (int i = start; i < target.size(); ++i) {
            if (!node->children.count(target[i])) break;
            node = node->children[target[i]];
            if (node->cost != INT_MAX) {
                dp[i + 1] = min(dp[i + 1], dp[start] + node->cost);
            }
        }
    }

    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        int n = target.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        unordered_map<string, int> word2cost;
        for (int i = 0; i < words.size(); i++) {
            if(word2cost.contains(words[i])) {
                word2cost[words[i]] = min(word2cost[words[i]], costs[i]);
                continue;
            }
            word2cost[words[i]] = costs[i];
        }
        // 构建字典树
        TrieNode* root = new TrieNode();
        for (auto &[k, v] : word2cost) {
            insert(root,k, v);
        }

        // 动态规划
        for (int i = 0; i < n; ++i) {
            if (dp[i] == INT_MAX) continue;
            search(root, target, i, dp);
        }

        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

int main(int argc, const char** argv) {
    Solution s;
    vector<string> words;
    vector<int> costs;
    debug(s.minimumCost("abcdef", words={"abdef","abc","d","def","ef"}, costs = {100,1,1,10,5}));
    return 0;
}
